package com.datastructure.test.maxvalueofslidewindow;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

public class MaxValueOfSlideWindow {

    ArrayList<Integer> res = new ArrayList<>();
    public static void main(String[] args) {
        int [] num = {2,3,4,2,6,2,5,1};
        MaxValueOfSlideWindow maxValueOfSlideWindow = new MaxValueOfSlideWindow();
        maxValueOfSlideWindow.maxInWindows2(num,3);
    }

    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        if(num.length<size){
            return res;
        }
        for(int i =0;i< num.length-size+1;i++){
            res.add(dfs(num[i], 0,size,i,num));
        }
        return res;
    }

    public int dfs(int max,int depth,int length,int indexI,int [] num){
        if(depth==length){
            return 0;
        }
        max = Math.max(max,num[indexI]);
        max=Math.max(max,dfs(max,depth+1,length,indexI+1,num));
        return max;
    }

    public ArrayList<Integer> maxInWindows1(int [] num, int size)
    {
        ArrayList<Integer> list = new ArrayList<>();
        if(num == null || num.length < size || size <= 0){
            return list;
        }
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < size; i++){//找到第一个窗口个的最大值
            if(num[i] > max){
                max = num[i];
            }
        }
        list.add(max);
        for(int i = size; i < num.length; i++){
            if(num[i] >= max){ //如果新来的大于max，更新max
                max = num[i];
            }else{ //否则，重新计算max
                max = num[i];
                for(int k = i - 1; k > i - size; k--){
                    if(num[k] > max){
                        max = num[k];
                    }
                }
            }
            list.add(max);
        }
        return list;
    }

    public ArrayList<Integer> maxInWindows2(int [] num, int size){
        if(num.length<size){
            return res;
        }
        int[] range;
        for(int i =0;i< num.length-size+1;i++){
            range = Arrays.copyOfRange(num, i, i + size);
            quickSort(range,0, range.length-1);
            res.add(range[size-1]);
        }
        return res;
    }

    public void quickSort(int[] arr,int left,int right){
        if(left<right){
            int mid = getIndex(arr,left,right);
            quickSort(arr,left,mid-1);
            quickSort(arr,mid+1,right);
        }
    }

    private int getIndex(int[] arr, int left, int right) {
        int oldValue = arr[left];
        int oldIndex = left;
        while (left<right){
            while (left<right&&arr[right]>=oldValue){
                right--;
            }
            while (left<right&&arr[left]<=oldValue){
                left++;
            }
            if(left<right){
                swap(arr,left,right);
            }
        }
        if(left==right){
            arr[oldIndex]=arr[left];
            arr[left]=oldValue;
        }
        return left;
    }

    public void swap(int[] arr,int left,int right){
        int temp = arr[left];
        arr[left]=arr[right];
        arr[right]=temp;
    }
}
